package chapter03;

import java.util.ArrayList;
import java.util.List;

public class SortedListToBST109 {
    /**
     * 快慢指针
     * 本题是[left,right]链表中找中间值 为了方便找中间节点的前一个节点 我们查找的范围左闭右开[left,right)
     * 快指针走两步 慢指针走一步 快指针走到right或者快指针下一步走到right时 慢指针就是中间节点
     * 递归出口
     *  1).left==right
     *      return null
     *  2).mid=getMid(left,right)
     *     cur=new TreeNode(mid.val)
     *     cur.left=process(left,mid)
     *     cur.right=process(mid.next,right)
     *     return cur
     */
    public class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   }

    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
   }

    public TreeNode sortedListToBST(ListNode head) {
        if(head==null){
            return null;
        }
        return process(head,null);
    }

    public TreeNode process(ListNode left, ListNode right){
        if(left==right){
            return null;
        }
        ListNode mid=getMid(left,right);
        TreeNode cur=new TreeNode(mid.val);
        cur.left=process(left,mid);
        cur.right=process(mid.next,right);
        return cur;
    }

    public ListNode getMid(ListNode left,ListNode right){
        ListNode fast=left;
        ListNode slow=left;
        while (fast!=right&&fast.next!=right){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}
